#include <bits/stdc++.h>

using namespace std;

// 二叉树的直径
// 给你一棵二叉树的根节点，返回该树的直径
// 二叉树的 直径 是指树中任意两个节点之间最长路径的长度
// 这条路径可能经过也可能不经过根节点 root
// 两节点之间路径的 长度 由它们之间边数表示
// 测试链接 : https://leetcode.cn/problems/diameter-of-binary-tree/

// 不需要提交这个类
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution 
{
private:
    struct Info
    {
        int diameter, height;
        Info(int a, int b)
        {
            diameter = a;
            height = b;
        }
    };

    Info f(TreeNode* x)
    {
        if(x == nullptr) return Info(0, 0);
        Info infol = f(x->left);
        Info infor = f(x->right);
        int height = max(infol.height, infor.height) + 1;
        int diameter = max(infol.diameter, infor.diameter);
        diameter = max(diameter, infol.height + infor.height);
        return Info(diameter, height);
    }

public:
    int diameterOfBinaryTree(TreeNode* root) 
    {
        return f(root).diameter;
    }
};


class Solution 
{
public:
    int diameterOfBinaryTree(TreeNode* root) 
    {
        int ret = INT_MIN;
        // dfs(x) : 以 x 为头的最长链长，不包含 x 自己
        function<int(TreeNode*)> dfs = [&](TreeNode* node)
        {
            if(!node) return -1;

            int left = dfs(node->left);
            int right = dfs(node->right);
            ret = max(ret, left + right + 2);
            return max(left, right) + 1;
        };
        dfs(root);
        return ret;
    }
};